{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CV2库应用-人脸识别\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1 opencv中人脸识别算法的基本原理   \n",
    "opencv中自带的三种人脸识别算法\n",
    "\n",
    "#### opencv人脸识别\n",
    "关于如何使用opencv实现人脸识别的过程可以参考：\n",
    "http://blog.csdn.net/wanghz999/article/details/78773643、\n",
    "http://blog.csdn.net/wanghz999/article/details/78776240\n",
    "这两篇博客。这里不再赘述。opencv支持3种人脸识别的算法，分别是：\n",
    "\n",
    "+ Eigen Faces\n",
    "+ Fisher Faces\n",
    "+ Local Binary Pattern Histograms(局部二值模式直方图)\n",
    "本文对三种算法的基本原理进行介绍。\n",
    "\n",
    "#### Eigenfaces的原理   \n",
    "Eigenfaces就是特征脸的意思，是一种从主成分分析（Principal Component Analysis，PCA）中导出的人脸识别和描述技术。特征脸方法的主要思路就是将输入的人脸图像看作一个个矩阵，通过在人脸空间中一组正交向量，并选择最重要的正交向量，作为“主成分”来描述原来的人脸空间。为了更好地理解特征脸方法，需要先了解PCA的主要过程。\n",
    "\n",
    "#### PCA的原理 \n",
    "在很多应用中，需要对大量数据进行分析计算并寻找其内在的规律，但是数据量巨大造成了问题分析的复杂性，因此我们需要一些合理的方法来减少分析的数据和变量同时尽量不破坏数据之间的关联性。于是这就有了主成分分析方法，PCA作用：\n",
    "\n",
    "1. 数据降维。减少变量个数；确保变量独立；提供一个合理的框架解释。\n",
    "2. 去除噪声，发现数据背后的固有模式。   \n",
    "\n",
    "PCA的主要过程：  \n",
    "1. 特征中心化：将每一维的数据（矩阵A）都减去该维的均值，使得变换后（矩阵B）每一维均值为0；\n",
    "2. 计算变换后矩阵B的协方差矩阵C；\n",
    "3. 计算协方差矩阵C的特征值和特征向量；\n",
    "4. 选取大的特征值对应的特征向量作为”主成分”，并构成新的数据集。   \n",
    "\n",
    "##### 特征脸方法   \n",
    "特征脸方法就是将PCA方法应用到人脸识别中，将人脸图像看成是原始数据集，使用PCA方法对其进行处理和降维，得到“主成分”——即特征脸，然后每个人脸都可以用特征脸的组合进行表示。这种方法的核心思路是认为同一类事物必然存在相同特性（主成分），通过将同一目标（人脸图像）的特性寻在出来，就可以用来区分不同的事物了。人脸识别嘛，就是一个分类的问题，将不同的人脸区分开来。特征脸方法的过程（先计算特征脸，然后识别人脸）：    \n",
    "1. 将训练集中的N个人脸拉成一列（reshape(1,1)），然后组合在一起形成一个大矩阵A。若人脸图像大小为m * m，则矩阵A的维度是m * m * N；\n",
    "2. 将N个人脸在对应的维度求平均，得到一个“平均脸”；\n",
    "3. 将矩阵A中N个图像都减去“平均脸”，得到新矩阵B；\n",
    "4. 计算B的协方差矩阵；\n",
    "5. 计算协方差矩阵的特征值和特征向量（特征脸）；\n",
    "6. 将训练集图像和测试集图像都投影到特征向量空间中，再使用聚类方法（最近邻或k近邻等）得到里测试集中的每个图像最近的图像，进行分类即可。   \n",
    "在opencv中```void EigenFaceRecognizer::train();```就是对训练集进行处理最终得到特征向量和阈值的过程，其中的阈值用于后面对测试图像的识别。```int EigenFaceRecognizer:: predict(InputArray src) const;```是对测试图像进行识别。   \n",
    "\n",
    "#### 特征脸识别的局限性   \n",
    "要让系统准确识别需要保证人脸图像满足：   \n",
    "1. 待识别图像中人脸尺寸接近特征脸中人脸的尺寸；\n",
    "2. 待识别人脸图像必须为正面人脸图像。\n",
    "3. 若不满足此条件，识别错误率很高。从PCA方法的过程可以看出，特征脸识别的方法是以每张人脸的一个维度（可以看出是矩阵的一列）为单位进行处理的，求得的特征向量（特征脸）中包含训练集每个纬度的绝大部分信息。但是若测试集中人脸尺寸不同，那么与特征脸中维度的也就没法对应起来。\n",
    "\n",
    "#### Fisherfaces\n",
    "在将Fisherfaces之前需要对线性判别进行一定的说明。\n",
    "\n",
    "### Fisher线性判别分析（linear discriminant analysis，LDA） \n",
    "线性判别分析是由Fisher提出的线性判别方法，可以用来处理两类的线性判别问题。两类的线性判别问题可以看做所有的样本投影到一个方向（或者说是一个维度空间中），然后再这个空间中确定一个分类的阈值。过这个阈值点且与投影方向垂直的超平面就是分类面。判别思路是选择投影方向，使得投影后两类相隔尽可能远，类内又尽可能聚集（类间方差最大，类内方差最小）。\n",
    "它的过程分为：  \n",
    "1. 确定最优的投影方向;\n",
    "2. 在这个方向上确定分类阈值。  \n",
    "#### Fisherfaces方法\n",
    "Fisherfaces方法结合了PCA和LDA的优点，其具体过程如下：\n",
    "\n",
    "1. PCA降维：对原始样本进行PCA处理，获取PCA处理之后的新样本；\n",
    "2. LDA特征提取：对降维后的样本使用Fisher线性判别方法，确定一个最优的投影方向，构造一个一维的特征空间（这就被称为Fisherfaces），将多维的人脸图像投影到Fisherfaces特征空间，利用类内样本数据形成一组特征向量，这组特征向量就代表了人脸的特征。    \n",
    "在opencv中void FisherFaceRecognizer::train();就是对训练集进行处理最终得到特征向量和阈值的过程，其中的阈值用于后面对测试图像的识别。int FisherFaceRecognizer:: predict(InputArray src) const;是对测试图像进行识别。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. 思路和核心代码\n",
    "### 思路如下：\n",
    "\n",
    "首先需要一个训练好的人脸和眼睛特征数据库，用于识别人脸和眼睛\n",
    "识别出人脸和眼睛之后，返回所在的区域（一般是矩形）\n",
    "把所在区域用一个矩形框框起来"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 获取摄像头视频"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "import cv2\n",
    "cap=cv2.VideoCapture(0)#0代表笔记本自带摄像头\n",
    "ok=True\n",
    "result=[]\n",
    "while ok: \n",
    "    ok,img=cap.read()\n",
    "    cv2.imshow('Video',img)\n",
    "    k=cv2.waitKey(1)\n",
    "    if k== 27 :\n",
    "        break\n",
    "cap.release()\n",
    "cv2.destroyAllWindows()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 人脸识别的一个框架"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 加载人脸识别数据库，生成一个对象\n",
    "faceCascadePath = \"cascades/haarcascade_frontalface_default.xml\"\n",
    "\n",
    "faceCascade = cv2.CascadeClassifier(faceCascadePath)\n",
    "gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)\n",
    "#### 识别出人脸的范围，返回一个矩形\n",
    "faceRects = faceCascade.detectMultiScale(gray, scaleFactor=1.1,\n",
    "                                         minNeighbors=5,minSize=(30,30),\\\n",
    "                                         flags = cv2.CASCADE_SCALE_IMAGE)\n",
    "#### 加载视频\n",
    "videoPath=\"\"\n",
    "video = cv2.VideoCapture(videoPath)\n",
    "#### 读取视频\n",
    "(grabbed,raw_frame) = video.read()\n",
    "#### 图像缩放\n",
    "#### 设置dim\n",
    "frame = cv2.resize(raw_frame,dim,interpolation=cv2.INTER_AREA)\n",
    "#### 识别出眼睛的范围，返回一个矩形\n",
    "eyeRects = eyeCascade.detectMultiScale(faceROI,\\\n",
    "                                               scaleFactor = 1.1, \\\n",
    "                                               minNeighbors = 10, \\\n",
    "                                               minSize = (20, 20),\\\n",
    "                                               flags = cv2.CASCADE_SCALE_IMAGE)\n",
    "#### 释放视频资源\n",
    "video.release()\n",
    "#### 关闭所有窗口\n",
    "cv2.destroyAllWindows()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 识别图像中的人脸\n",
    "### 首先进行人脸识别"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "import cv2\n",
    "# 加载图像\n",
    "image = cv2.imread(\"images/dyc.jpg\")\n",
    "#image = cv2.imread(\"images/obama2.png\")\n",
    "#image = cv2.imread(\"images/messi.png\")\n",
    "#image = cv2.imread(\"images/messi2.png\")\n",
    "# 测试是否成功读取\n",
    "image=cv2.resize(image,dsize=(768,1024))\n",
    "cv2.imshow(\"raw\",image)\n",
    "cv2.waitKey(0)\n",
    "# 进行灰度处理\n",
    "gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)\n",
    "# cv2.imshow(\"gray\",gray)\n",
    "# cv2.waitKey(0)\n",
    "# 加载人脸识别数据库\n",
    "faceCascadePath = \"cascades/haarcascade_frontalface_default.xml\"\n",
    "faceCascade = cv2.CascadeClassifier(faceCascadePath)\n",
    "faceRects = faceCascade.detectMultiScale(gray,scaleFactor=1.1,\\\n",
    "                                         minNeighbors=5,minSize=(30,30),\\\n",
    "                                         flags = cv2.CASCADE_SCALE_IMAGE)\n",
    "for (x,y,w,h) in faceRects:\n",
    "    cv2.rectangle(image,(x,y),(x+w,y+h),(0,255,0),2)\n",
    "cv2.imshow(\"Found {} faces in the picture\".format(len(faceRects)),image)    \n",
    "cv2.waitKey(0)\n",
    "cv2.destroyAllWindows()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "识别视频中的人脸和眼睛\n",
    "和图片很像，只需要把视频按照帧分解就可以了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 首先读取视频\n",
    "videoPath = \"video/img_4524.MP4\"\n",
    "video = cv2.VideoCapture(videoPath)\n",
    "\n",
    "while True:\n",
    "    # grabbed验证视频是否成功读取\n",
    "    (grabbed,raw_frame) = video.read()\n",
    "    if not grabbed:\n",
    "        break\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import cv2\n",
    "# 首先读取视频\n",
    "videoPath = \"video/img_4524.mp4\"\n",
    "video = cv2.VideoCapture(videoPath) \n",
    "facesample=cv2.imread(\"images/dyc.jpg\")\n",
    "###\n",
    "\n",
    "font = cv2.FONT_HERSHEY_DUPLEX\n",
    "\n",
    "###\n",
    "while True:\n",
    "    # grabbed验证视频是否成功读取\n",
    "    (grabbed,raw_frame) = video.read()\n",
    "    if not grabbed:\n",
    "        break\n",
    "\t# 进行图像缩放\n",
    "    (height,width) = raw_frame.shape[:2]\n",
    "    ratio = 900/width\n",
    "    dim = (900,int(height*ratio))\n",
    "    frame = cv2.resize(raw_frame,dim,interpolation=cv2.INTER_AREA)\n",
    "    # 进行灰度处理\n",
    "    gray = cv2.cvtColor(frame,cv2.COLOR_BGR2GRAY)\n",
    "    \n",
    "\t# 加载人脸识别数据库和眼睛识别数据库\n",
    "    faceCascadePath = \"cascades/haarcascade_frontalface_default.xml\"\n",
    "    profiefaceCascadePath = \"cascades/haarcascade_profileface.xml\"\n",
    "    eyeCascadePath  = \"cascades/haarcascade_eye.xml\"\n",
    "    #\n",
    "    faceCascade = cv2.CascadeClassifier(faceCascadePath)\n",
    "    eyeCascade  = cv2.CascadeClassifier(eyeCascadePath)\n",
    "    ProfilefaceCascade = cv2.CascadeClassifier(profiefaceCascadePath)\n",
    "    # 进行人脸识别，返回人脸所在的矩形\n",
    "    faceRects = faceCascade.detectMultiScale(frame,\\\n",
    "                                             scaleFactor = 1.13, \\\n",
    "                                             minNeighbors = 5, \\\n",
    "                                             minSize = (20, 20),\\\n",
    "                                             flags = cv2.CASCADE_SCALE_IMAGE)\n",
    "\n",
    "    \n",
    "    faceRects_list=[]\n",
    "    eyerects_list=[]                                       \n",
    "    for (fx,fy,fw,fh) in faceRects: \n",
    "        \n",
    "        # region of interest:faceROI\n",
    "        faceROI = frame[fy:fy+fh,fx:fx+fw]\n",
    "        # 以两个对角线坐标的形式保存\n",
    "        faceRects_list.append((fx,fy,fx+fw,fy+fh))\n",
    "        # 进行眼睛识别，返回眼睛所在的矩形\n",
    "        eyeRects = eyeCascade.detectMultiScale(faceROI,\\\n",
    "                                               scaleFactor = 1.15, \\\n",
    "                                               minNeighbors = 10, \\\n",
    "                                               minSize = (30, 30),\\\n",
    "                                               flags = cv2.CASCADE_SCALE_IMAGE)\n",
    "        for (ex,ey,ew,eh) in eyeRects:\n",
    "            # 同样也以两个对角线坐标的形式保存，注意眼睛的参考坐标系是faceROI\n",
    "            eysrects_list.append((fx+ex,fy+ey,fx+ex+ew,fy+ey+eh))\n",
    "    \n",
    "    # 在视频帧上绘制出识别出来的矩形框框\n",
    "    for rect in faceRects:\n",
    "        (fx,fy,fw,fh) = rect\n",
    "        cv2.rectangle(frame,(fx,fy),(fx+fw,fy+fh),(0,255,0),2)\n",
    "    cv2.imshow(\"tracking\",frame)\n",
    "    # 等待1ms\n",
    "    key=cv2.waitKey(1)\n",
    "    if key==27: \n",
    "         break\n",
    "\n",
    "# 释放资源和窗口\n",
    "video.release()\n",
    "cv2.destroyAllWindows()\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## opencv实现人脸识别（三） 训练图片模块\n",
    "现在我们已经拍好了需要训练的图片，接下来就是进行训练对于视频的质量要求比较高，干扰比较大。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import datetime as dt\n",
    "import numpy as np\n",
    "\n",
    "n = 100000\n",
    "start = dt.datetime.now()\n",
    "A, B = [], []\n",
    "for i in range(n):\n",
    "    A.append(i ** 2)\n",
    "    B.append(i ** 3)\n",
    "C = []\n",
    "for a,b in zip(A,B):\n",
    "    C.append(a+b)\n",
    "\n",
    "t = (dt.datetime.now() -start).microseconds\n",
    "print(t)\n",
    "start = dt.datetime.now()\n",
    "A, B = np.arange(n)**2, np.arange(n)**3\n",
    "C = A+B\n",
    "t = (dt.datetime.now() - start).microseconds\n",
    "print(t)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "训练模块的源代码："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'4.7.0'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "from PIL import Image\n",
    "import os\n",
    "import cv2\n",
    "#import face_recognition_models \n",
    "cv2.__version__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 faces trained.\n"
     ]
    }
   ],
   "source": [
    "\n",
    "def train():\n",
    "    path = '.\\\\Facedata\\\\1'\n",
    "\n",
    "    # 创建opencv中的LBPH算法的人脸识别器\n",
    "    recognizer = cv2.face.LBPHFaceRecognizer_create()\n",
    "    # 依然是运用人脸识别分类器\n",
    "    detector = cv2.CascadeClassifier('./cascades/haarcascade_frontalface_default.xml')\n",
    "\n",
    "    def getImagesAndLabels(path):\n",
    "        # os.path.join()函数：\n",
    "        # 连接两个或更多的路径名组件\n",
    "        # os.listdir() 方法\n",
    "        # 用于返回指定的文件夹包含的文件或文件夹的名字的列表。这个列表以字母顺序排列\n",
    "        imagePaths = [os.path.join(path, f)for f in os.listdir(path)]\n",
    "\n",
    "        faceSamples = []\n",
    "        ids = []\n",
    "\n",
    "        # 遍历每一张拍到的图片\n",
    "        for imagePath in imagePaths:\n",
    "            # 打开图片，并转换成灰度图\n",
    "            PIL_img = Image.open(imagePath).convert('L')\n",
    "\n",
    "            # 将原图片的多维数组转为numpy的数组\n",
    "            img_numpy = np.array(PIL_img, 'uint8')\n",
    "\n",
    "            # id对应的值是当前用户的第几张照片\n",
    "            id = int(os.path.split(imagePath)[1].split('.')[0])\n",
    "            \n",
    "\n",
    "            # 检测人脸\n",
    "            faces = detector.detectMultiScale(img_numpy)\n",
    "            for(x, y, w, h) in faces:\n",
    "                # 将人脸范围的numpy数组数据保存到列表中\n",
    "                faceSamples.append(img_numpy[y : y + h, x : x + w])\n",
    "                # 将id值保存到列表中\n",
    "                ids.append(id)\n",
    "            return faceSamples, ids\n",
    "\n",
    "    faces, ids = getImagesAndLabels(path)\n",
    "\n",
    "    # 对图片进行训练，将训练文件保存在指定路径\n",
    "    recognizer.train(faces, np.array(ids))\n",
    "    recognizer.write(r'cascades\\trainer.yml')\n",
    "    print('{0} faces trained.'.format(len(np.unique(ids))))\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    train()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "\n",
    "path = '.\\\\Facedata\\\\1\\\\1.jpg'\n",
    "print(os.path.split(path)[1].split('.')[0])"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "opencv实现人脸识别（四） 人脸识别模块"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1\n",
      "1 1\n",
      "1 1\n",
      "1 1\n",
      "1 2\n",
      "1 2\n",
      "1 2\n",
      "1 2\n",
      "1 2\n",
      "1 3\n",
      "1 3\n",
      "1 3\n",
      "1 3\n",
      "1 3\n",
      "1 4\n",
      "1 4\n",
      "1 4\n",
      "1 4\n",
      "1 4\n",
      "1 5\n",
      "1 5\n",
      "1 5\n",
      "1 5\n",
      "1 5\n",
      "1 5\n",
      "1 6\n",
      "1 6\n",
      "1 6\n",
      "1 6\n",
      "1 6\n",
      "1 7\n",
      "1 7\n",
      "1 7\n",
      "1 7\n",
      "1 8\n",
      "1 8\n",
      "1 8\n",
      "1 8\n",
      "1 9\n",
      "1 9\n",
      "1 9\n",
      "1 9\n",
      "1 10\n",
      "1 10\n",
      "1 10\n",
      "1 11\n",
      "1 11\n",
      "1 11\n",
      "1 11\n",
      "1 12\n",
      "1 12\n",
      "1 12\n",
      "1 12\n",
      "1 13\n",
      "1 13\n",
      "1 13\n",
      "1 13\n",
      "1 14\n",
      "1 14\n",
      "1 14\n",
      "1 14\n",
      "1 14\n",
      "1 15\n",
      "1 15\n",
      "1 15\n",
      "1 15\n",
      "1 15\n",
      "1 16\n",
      "1 16\n",
      "1 16\n",
      "1 16\n",
      "1 17\n",
      "1 17\n",
      "1 17\n",
      "1 18\n",
      "1 18\n",
      "1 18\n",
      "1 19\n",
      "1 19\n",
      "1 19\n",
      "1 20\n",
      "1 20\n",
      "1 20\n",
      "1 21\n",
      "1 21\n",
      "1 21\n",
      "1 22\n",
      "1 22\n",
      "1 22\n",
      "1 23\n",
      "1 23\n",
      "1 23\n",
      "1 23\n",
      "1 24\n",
      "1 24\n",
      "1 24\n",
      "1 25\n",
      "1 25\n",
      "1 25\n",
      "1 26\n",
      "1 26\n",
      "1 26\n",
      "1 27\n",
      "1 27\n",
      "1 27\n",
      "1 28\n",
      "1 28\n",
      "1 28\n",
      "1 28\n",
      "1 29\n",
      "1 29\n",
      "1 29\n",
      "1 30\n",
      "1 30\n",
      "1 30\n",
      "1 31\n",
      "1 31\n",
      "1 31\n",
      "1 31\n",
      "1 31\n",
      "1 31\n",
      "1 32\n",
      "1 32\n",
      "1 32\n",
      "1 32\n",
      "1 32\n",
      "1 32\n",
      "1 33\n",
      "1 33\n",
      "1 33\n",
      "1 33\n",
      "1 34\n",
      "1 34\n",
      "1 34\n",
      "1 34\n",
      "1 34\n",
      "1 35\n",
      "1 35\n",
      "1 35\n",
      "1 35\n",
      "1 36\n",
      "1 36\n",
      "1 36\n",
      "1 36\n",
      "1 36\n",
      "1 36\n",
      "1 37\n",
      "1 37\n",
      "1 37\n",
      "1 37\n",
      "1 37\n",
      "1 38\n",
      "1 38\n",
      "1 38\n",
      "1 38\n",
      "1 38\n",
      "1 39\n",
      "1 39\n",
      "1 39\n",
      "1 39\n",
      "1 39\n",
      "1 40\n",
      "1 40\n",
      "1 40\n",
      "1 40\n",
      "1 41\n",
      "1 41\n",
      "1 41\n",
      "1 41\n",
      "1 42\n",
      "1 42\n",
      "1 42\n",
      "1 43\n",
      "1 43\n",
      "1 43\n",
      "1 44\n",
      "1 44\n",
      "1 44\n",
      "1 45\n",
      "1 46\n",
      "1 46\n",
      "1 46\n",
      "1 47\n",
      "1 48\n",
      "1 48\n",
      "1 48\n",
      "1 49\n",
      "1 50\n",
      "1 50\n",
      "1 51\n",
      "1 51\n",
      "1 52\n",
      "1 52\n",
      "1 52\n",
      "1 53\n",
      "1 54\n",
      "1 54\n",
      "1 55\n",
      "1 56\n",
      "1 56\n",
      "1 56\n",
      "1 57\n",
      "1 57\n",
      "1 57\n",
      "1 58\n",
      "1 58\n",
      "1 59\n",
      "1 59\n",
      "1 59\n",
      "1 59\n",
      "1 59\n",
      "1 59\n",
      "1 60\n",
      "1 60\n",
      "1 60\n",
      "1 60\n",
      "1 60\n",
      "1 60\n",
      "1 61\n",
      "1 61\n",
      "1 61\n",
      "1 61\n",
      "1 61\n",
      "1 61\n",
      "1 61\n",
      "1 62\n",
      "1 62\n",
      "1 62\n",
      "1 62\n",
      "1 62\n",
      "1 62\n",
      "1 62\n",
      "1 62\n",
      "1 62\n",
      "1 63\n",
      "1 63\n",
      "1 63\n",
      "1 63\n",
      "1 63\n",
      "1 63\n",
      "1 63\n",
      "1 63\n",
      "1 64\n",
      "1 64\n",
      "1 64\n",
      "1 64\n",
      "1 64\n",
      "1 64\n",
      "1 65\n",
      "1 65\n",
      "1 65\n",
      "1 65\n",
      "1 65\n",
      "1 65\n",
      "1 65\n",
      "1 66\n",
      "1 66\n",
      "1 66\n",
      "1 66\n",
      "1 66\n",
      "1 66\n",
      "1 66\n",
      "1 67\n",
      "1 67\n",
      "1 67\n",
      "1 67\n",
      "1 67\n",
      "1 67\n",
      "1 67\n",
      "1 67\n",
      "1 68\n",
      "1 68\n",
      "1 68\n",
      "1 68\n",
      "1 68\n",
      "1 68\n",
      "1 69\n",
      "1 69\n",
      "1 69\n",
      "1 69\n",
      "1 69\n",
      "1 70\n",
      "1 70\n",
      "1 70\n",
      "1 70\n",
      "1 70\n",
      "1 70\n",
      "1 70\n",
      "1 71\n",
      "1 71\n",
      "1 71\n",
      "1 71\n",
      "1 71\n",
      "1 71\n",
      "1 72\n",
      "1 72\n",
      "1 72\n",
      "1 72\n",
      "1 72\n",
      "1 72\n",
      "1 73\n",
      "1 73\n",
      "1 73\n",
      "1 73\n",
      "1 73\n",
      "1 73\n",
      "1 74\n",
      "1 74\n",
      "1 74\n",
      "1 74\n",
      "1 74\n",
      "1 74\n",
      "1 74\n",
      "1 75\n",
      "1 75\n",
      "1 75\n",
      "1 75\n",
      "1 75\n",
      "1 76\n",
      "1 76\n",
      "1 76\n",
      "1 76\n",
      "1 76\n",
      "1 76\n",
      "1 77\n",
      "1 77\n",
      "1 77\n",
      "1 77\n",
      "1 77\n",
      "1 78\n",
      "1 78\n",
      "1 78\n",
      "1 78\n",
      "1 78\n",
      "1 79\n",
      "1 79\n",
      "1 79\n",
      "1 79\n",
      "1 79\n",
      "1 79\n",
      "1 80\n",
      "1 80\n",
      "1 80\n",
      "1 80\n",
      "1 80\n",
      "1 81\n",
      "1 81\n",
      "1 81\n",
      "1 81\n",
      "1 81\n",
      "1 81\n",
      "1 81\n",
      "1 82\n",
      "1 82\n",
      "1 82\n",
      "1 82\n",
      "1 82\n",
      "1 82\n",
      "1 82\n",
      "1 83\n",
      "1 83\n",
      "1 83\n",
      "1 83\n",
      "1 83\n",
      "1 83\n",
      "1 84\n",
      "1 84\n",
      "1 84\n",
      "1 84\n",
      "1 84\n",
      "1 84\n",
      "1 84\n",
      "1 85\n",
      "1 85\n",
      "1 85\n",
      "1 85\n",
      "1 85\n",
      "1 85\n",
      "1 86\n",
      "1 86\n",
      "1 86\n",
      "1 86\n",
      "1 86\n",
      "1 86\n",
      "1 87\n",
      "1 87\n",
      "1 87\n",
      "1 87\n",
      "1 87\n",
      "1 87\n",
      "1 87\n",
      "1 87\n",
      "1 88\n",
      "1 88\n",
      "1 88\n",
      "1 88\n",
      "1 88\n",
      "1 88\n",
      "1 88\n",
      "1 88\n",
      "1 89\n",
      "1 89\n",
      "1 89\n",
      "1 89\n",
      "1 89\n",
      "1 89\n",
      "1 89\n",
      "1 90\n",
      "1 90\n",
      "1 90\n",
      "1 90\n",
      "1 90\n",
      "1 90\n",
      "1 90\n",
      "1 90\n",
      "1 91\n",
      "1 91\n",
      "1 91\n",
      "1 91\n",
      "1 91\n",
      "1 91\n",
      "1 91\n",
      "1 91\n",
      "1 92\n",
      "1 92\n",
      "1 92\n",
      "1 92\n",
      "1 92\n",
      "1 92\n",
      "1 92\n",
      "1 92\n",
      "1 93\n",
      "1 93\n",
      "1 93\n",
      "1 93\n",
      "1 93\n",
      "1 93\n",
      "1 94\n",
      "1 94\n",
      "1 94\n",
      "1 94\n",
      "1 94\n",
      "1 94\n",
      "1 94\n",
      "1 95\n",
      "1 95\n",
      "1 95\n",
      "1 95\n",
      "1 95\n",
      "1 95\n",
      "1 95\n",
      "1 95\n",
      "1 96\n",
      "1 96\n",
      "1 96\n",
      "1 96\n",
      "1 96\n",
      "1 96\n",
      "1 96\n",
      "1 96\n",
      "1 97\n",
      "1 97\n",
      "1 97\n",
      "1 97\n",
      "1 97\n",
      "1 97\n",
      "1 97\n",
      "1 98\n",
      "1 98\n",
      "1 98\n",
      "1 98\n",
      "1 98\n",
      "1 98\n",
      "1 98\n",
      "1 99\n",
      "1 99\n",
      "1 99\n",
      "1 99\n",
      "1 99\n",
      "1 99\n",
      "1 99\n",
      "1 100\n",
      "1 100\n",
      "1 100\n",
      "1 100\n",
      "1 100\n",
      "1 100\n",
      "1 100\n",
      "1 101\n",
      "1 101\n",
      "1 101\n",
      "1 101\n",
      "1 101\n",
      "1 101\n",
      "1 101\n",
      "1 102\n",
      "1 102\n",
      "1 102\n",
      "1 102\n",
      "1 102\n",
      "1 102\n",
      "1 102\n",
      "1 103\n",
      "1 103\n",
      "1 103\n",
      "1 103\n",
      "1 103\n",
      "1 103\n",
      "1 103\n",
      "1 103\n",
      "1 104\n",
      "1 104\n",
      "1 104\n",
      "1 104\n",
      "1 104\n",
      "1 104\n",
      "1 104\n",
      "1 105\n",
      "1 105\n",
      "1 105\n",
      "1 105\n",
      "1 105\n",
      "1 105\n",
      "1 105\n",
      "1 106\n",
      "1 106\n",
      "1 106\n",
      "1 106\n",
      "1 106\n",
      "1 106\n",
      "1 106\n",
      "1 107\n",
      "1 107\n",
      "1 107\n",
      "1 107\n",
      "1 107\n",
      "1 107\n",
      "1 108\n",
      "1 108\n",
      "1 108\n",
      "1 108\n",
      "1 108\n",
      "1 108\n",
      "1 109\n",
      "1 109\n",
      "1 109\n",
      "1 109\n",
      "1 109\n",
      "1 109\n",
      "1 110\n",
      "1 110\n",
      "1 110\n",
      "1 110\n",
      "1 110\n",
      "1 111\n",
      "1 111\n",
      "1 111\n",
      "1 111\n",
      "1 111\n",
      "1 112\n",
      "1 112\n",
      "1 112\n",
      "1 112\n",
      "1 112\n",
      "1 112\n",
      "1 113\n",
      "1 113\n",
      "1 113\n",
      "1 113\n",
      "1 113\n",
      "1 113\n",
      "1 113\n",
      "1 114\n",
      "1 114\n",
      "1 114\n",
      "1 114\n",
      "1 114\n",
      "1 115\n",
      "1 115\n",
      "1 115\n",
      "1 115\n",
      "1 115\n",
      "1 115\n",
      "1 115\n",
      "1 116\n",
      "1 116\n",
      "1 116\n",
      "1 116\n",
      "1 116\n",
      "1 116\n",
      "1 117\n",
      "1 117\n",
      "1 117\n",
      "1 117\n",
      "1 117\n",
      "1 117\n",
      "1 118\n",
      "1 118\n",
      "1 118\n",
      "1 118\n",
      "1 118\n",
      "1 119\n",
      "1 119\n",
      "1 119\n",
      "1 119\n",
      "1 119\n",
      "1 120\n",
      "1 120\n",
      "1 120\n",
      "1 120\n",
      "1 120\n",
      "1 120\n",
      "1 120\n",
      "1 121\n",
      "1 121\n",
      "1 121\n",
      "1 121\n",
      "1 121\n",
      "1 122\n",
      "1 122\n",
      "1 122\n",
      "1 122\n",
      "1 122\n",
      "1 122\n",
      "1 123\n",
      "1 123\n",
      "1 123\n",
      "1 123\n",
      "1 123\n",
      "1 123\n",
      "1 124\n",
      "1 124\n",
      "1 124\n",
      "1 124\n",
      "1 124\n",
      "1 125\n",
      "1 125\n",
      "1 125\n",
      "1 125\n",
      "1 126\n",
      "1 126\n",
      "1 126\n",
      "1 126\n",
      "1 127\n",
      "1 127\n",
      "1 127\n",
      "1 127\n",
      "1 127\n",
      "1 128\n",
      "1 128\n",
      "1 128\n",
      "1 128\n",
      "1 129\n",
      "1 129\n",
      "1 129\n",
      "1 129\n",
      "1 130\n",
      "1 130\n",
      "1 130\n",
      "1 130\n",
      "1 131\n",
      "1 131\n",
      "1 131\n",
      "1 131\n",
      "1 132\n",
      "1 132\n",
      "1 132\n",
      "1 132\n",
      "1 133\n",
      "1 133\n",
      "1 133\n",
      "1 133\n",
      "1 134\n",
      "1 134\n",
      "1 134\n",
      "1 134\n",
      "1 134\n",
      "1 134\n",
      "1 135\n",
      "1 135\n",
      "1 135\n",
      "1 135\n",
      "1 135\n",
      "1 136\n",
      "1 136\n",
      "1 136\n",
      "1 136\n",
      "1 136\n",
      "1 136\n",
      "1 137\n",
      "1 137\n",
      "1 137\n",
      "1 137\n",
      "1 137\n",
      "1 137\n",
      "1 137\n",
      "1 138\n",
      "1 138\n",
      "1 138\n",
      "1 138\n",
      "1 138\n",
      "1 139\n",
      "1 139\n",
      "1 139\n",
      "1 139\n",
      "1 139\n",
      "1 139\n",
      "1 139\n",
      "1 140\n",
      "1 140\n",
      "1 140\n",
      "1 140\n",
      "1 140\n",
      "1 140\n",
      "1 140\n",
      "1 141\n",
      "1 141\n",
      "1 141\n",
      "1 141\n",
      "1 141\n",
      "1 141\n",
      "1 141\n",
      "1 142\n",
      "1 142\n",
      "1 142\n",
      "1 142\n",
      "1 142\n",
      "1 142\n",
      "1 142\n",
      "1 143\n",
      "1 143\n",
      "1 143\n",
      "1 143\n",
      "1 143\n",
      "1 143\n",
      "1 143\n",
      "1 144\n",
      "1 144\n",
      "1 144\n",
      "1 144\n",
      "1 144\n",
      "1 144\n",
      "1 144\n",
      "1 145\n",
      "1 145\n",
      "1 145\n",
      "1 145\n",
      "1 145\n",
      "1 145\n",
      "1 145\n",
      "1 146\n",
      "1 146\n",
      "1 146\n",
      "1 146\n",
      "1 146\n",
      "1 146\n",
      "1 146\n",
      "1 147\n",
      "1 147\n",
      "1 147\n",
      "1 147\n",
      "1 147\n",
      "1 147\n",
      "1 148\n",
      "1 148\n",
      "1 148\n",
      "1 148\n",
      "1 148\n",
      "1 148\n",
      "1 148\n",
      "1 149\n",
      "1 149\n",
      "1 149\n",
      "1 149\n",
      "1 149\n",
      "1 149\n",
      "1 150\n",
      "1 150\n",
      "1 150\n",
      "1 150\n",
      "1 150\n",
      "1 150\n",
      "1 150\n",
      "1 151\n",
      "1 151\n",
      "1 151\n",
      "1 151\n",
      "1 151\n",
      "1 151\n",
      "1 152\n",
      "1 152\n",
      "1 152\n",
      "1 152\n",
      "1 152\n",
      "1 152\n",
      "1 152\n",
      "1 152\n",
      "1 153\n",
      "1 153\n",
      "1 153\n",
      "1 153\n",
      "1 153\n",
      "1 153\n",
      "1 154\n",
      "1 154\n",
      "1 154\n",
      "1 154\n",
      "1 154\n",
      "1 154\n",
      "1 155\n",
      "1 155\n",
      "1 155\n",
      "1 155\n",
      "1 155\n",
      "1 155\n",
      "1 156\n",
      "1 156\n",
      "1 156\n",
      "1 156\n",
      "1 156\n",
      "1 156\n",
      "1 157\n",
      "1 157\n",
      "1 157\n",
      "1 157\n",
      "1 157\n",
      "1 157\n",
      "1 158\n",
      "1 158\n",
      "1 158\n",
      "1 158\n",
      "1 158\n",
      "1 158\n",
      "1 158\n",
      "1 159\n",
      "1 159\n",
      "1 159\n",
      "1 159\n",
      "1 159\n",
      "1 159\n",
      "1 159\n",
      "1 160\n",
      "1 160\n",
      "1 160\n",
      "1 160\n",
      "1 160\n",
      "1 160\n",
      "1 160\n",
      "1 161\n",
      "1 161\n",
      "1 161\n",
      "1 161\n",
      "1 161\n",
      "1 161\n",
      "1 161\n",
      "1 162\n",
      "1 162\n",
      "1 162\n",
      "1 162\n",
      "1 162\n",
      "1 162\n",
      "1 162\n",
      "1 163\n",
      "1 163\n",
      "1 163\n",
      "1 163\n",
      "1 163\n",
      "1 163\n",
      "1 163\n",
      "1 164\n",
      "1 164\n",
      "1 164\n",
      "1 164\n",
      "1 164\n",
      "1 164\n",
      "1 164\n",
      "1 165\n",
      "1 165\n",
      "1 165\n",
      "1 165\n",
      "1 165\n",
      "1 165\n",
      "1 165\n",
      "1 166\n",
      "1 166\n",
      "1 166\n",
      "1 166\n",
      "1 166\n",
      "1 166\n",
      "1 166\n",
      "1 167\n",
      "1 167\n",
      "1 167\n",
      "1 167\n",
      "1 167\n",
      "1 167\n",
      "1 167\n",
      "1 168\n",
      "1 168\n",
      "1 168\n",
      "1 168\n",
      "1 168\n",
      "1 168\n",
      "1 168\n",
      "1 169\n",
      "1 169\n",
      "1 169\n",
      "1 169\n",
      "1 169\n",
      "1 169\n",
      "1 169\n",
      "1 169\n",
      "1 170\n",
      "1 170\n",
      "1 170\n",
      "1 170\n",
      "1 170\n",
      "1 170\n",
      "1 170\n",
      "1 171\n",
      "1 171\n",
      "1 171\n",
      "1 171\n",
      "1 171\n",
      "1 171\n",
      "1 171\n",
      "1 172\n",
      "1 172\n",
      "1 172\n",
      "1 172\n",
      "1 172\n",
      "1 172\n",
      "1 173\n",
      "1 173\n",
      "1 173\n",
      "1 173\n",
      "1 173\n",
      "1 173\n",
      "1 173\n",
      "1 174\n",
      "1 174\n",
      "1 174\n",
      "1 174\n",
      "1 174\n",
      "1 174\n",
      "1 174\n",
      "1 174\n",
      "1 175\n",
      "1 175\n",
      "1 175\n",
      "1 175\n",
      "1 175\n",
      "1 175\n",
      "1 175\n",
      "1 175\n",
      "1 176\n",
      "1 176\n",
      "1 176\n",
      "1 176\n",
      "1 176\n",
      "1 176\n",
      "1 176\n",
      "1 177\n",
      "1 177\n",
      "1 177\n",
      "1 177\n",
      "1 177\n",
      "1 177\n",
      "1 178\n",
      "1 178\n",
      "1 178\n",
      "1 178\n",
      "1 178\n",
      "1 178\n",
      "1 178\n",
      "1 179\n",
      "1 179\n",
      "1 180\n",
      "1 180\n",
      "1 180\n",
      "1 180\n",
      "1 180\n",
      "1 180\n",
      "1 180\n",
      "1 181\n",
      "1 181\n",
      "1 181\n",
      "1 181\n",
      "1 181\n",
      "1 181\n",
      "1 181\n",
      "1 181\n",
      "1 182\n",
      "1 182\n",
      "1 182\n",
      "1 182\n",
      "1 182\n",
      "1 182\n",
      "1 182\n",
      "1 182\n",
      "1 183\n",
      "1 183\n",
      "1 183\n",
      "1 183\n",
      "1 183\n",
      "1 183\n",
      "1 183\n",
      "1 183\n",
      "1 184\n",
      "1 184\n",
      "1 184\n",
      "1 184\n",
      "1 184\n",
      "1 184\n",
      "1 184\n",
      "1 184\n",
      "1 185\n",
      "1 185\n",
      "1 185\n",
      "1 185\n",
      "1 185\n",
      "1 185\n",
      "1 185\n",
      "1 186\n",
      "1 186\n",
      "1 186\n",
      "1 186\n",
      "1 186\n",
      "1 186\n",
      "1 186\n",
      "1 186\n",
      "1 186\n",
      "1 187\n",
      "1 187\n",
      "1 187\n",
      "1 187\n",
      "1 187\n",
      "1 187\n",
      "1 187\n",
      "1 187\n",
      "1 187\n",
      "1 188\n",
      "1 188\n",
      "1 188\n",
      "1 188\n",
      "1 188\n",
      "1 188\n",
      "1 188\n",
      "1 188\n",
      "1 188\n",
      "1 189\n",
      "1 189\n",
      "1 189\n",
      "1 189\n",
      "1 189\n",
      "1 189\n",
      "1 189\n",
      "1 190\n",
      "1 191\n",
      "1 191\n",
      "1 192\n",
      "1 193\n",
      "1 193\n",
      "1 194\n",
      "1 194\n",
      "1 194\n",
      "1 194\n",
      "1 194\n",
      "1 195\n",
      "1 195\n",
      "1 198\n",
      "1 201\n",
      "1 203\n",
      "1 203\n",
      "1 204\n",
      "1 205\n",
      "1 205\n",
      "1 205\n",
      "1 206\n",
      "1 206\n",
      "1 206\n",
      "1 206\n",
      "1 206\n",
      "1 207\n",
      "1 207\n",
      "1 207\n",
      "1 207\n",
      "1 207\n",
      "1 208\n",
      "1 208\n",
      "1 208\n",
      "1 209\n",
      "1 209\n",
      "1 209\n",
      "1 209\n",
      "1 209\n",
      "1 210\n",
      "1 210\n",
      "1 210\n",
      "1 210\n",
      "1 210\n",
      "1 210\n",
      "1 211\n",
      "1 211\n",
      "1 211\n",
      "1 211\n",
      "1 211\n",
      "1 212\n",
      "1 212\n",
      "1 212\n",
      "1 212\n",
      "1 212\n",
      "1 213\n",
      "1 213\n",
      "1 213\n",
      "1 213\n",
      "1 213\n",
      "1 213\n",
      "1 214\n",
      "1 214\n",
      "1 214\n",
      "1 214\n",
      "1 214\n",
      "1 214\n",
      "1 214\n",
      "1 215\n",
      "1 215\n",
      "1 215\n",
      "1 215\n",
      "1 215\n",
      "1 215\n",
      "1 215\n",
      "1 215\n",
      "1 216\n",
      "1 216\n",
      "1 216\n",
      "1 216\n",
      "1 216\n",
      "1 216\n",
      "1 216\n",
      "1 217\n",
      "1 217\n",
      "1 217\n",
      "1 217\n",
      "1 217\n",
      "1 217\n",
      "1 217\n",
      "1 218\n",
      "1 218\n",
      "1 218\n",
      "1 218\n",
      "1 218\n",
      "1 218\n",
      "1 218\n",
      "1 218\n",
      "1 219\n",
      "1 219\n",
      "1 219\n",
      "1 219\n",
      "1 219\n",
      "1 219\n",
      "1 219\n",
      "1 219\n",
      "1 220\n",
      "1 220\n",
      "1 220\n",
      "1 220\n",
      "1 220\n",
      "1 220\n",
      "1 220\n",
      "1 221\n",
      "1 221\n",
      "1 221\n",
      "1 221\n",
      "1 221\n",
      "1 221\n",
      "1 221\n",
      "1 221\n",
      "1 222\n",
      "1 222\n",
      "1 222\n",
      "1 222\n",
      "1 222\n",
      "1 222\n",
      "1 223\n",
      "1 223\n",
      "1 223\n",
      "1 223\n",
      "1 223\n",
      "1 223\n",
      "1 224\n",
      "1 224\n",
      "1 224\n",
      "1 224\n",
      "1 224\n",
      "1 224\n",
      "1 225\n",
      "1 225\n",
      "1 225\n",
      "1 225\n",
      "1 225\n",
      "1 225\n",
      "1 225\n",
      "1 225\n",
      "1 226\n",
      "1 226\n",
      "1 226\n",
      "1 226\n",
      "1 226\n",
      "1 226\n",
      "1 227\n",
      "1 227\n",
      "1 227\n",
      "1 227\n",
      "1 227\n",
      "1 227\n",
      "1 227\n",
      "1 228\n",
      "1 228\n",
      "1 228\n",
      "1 228\n",
      "1 228\n",
      "1 228\n",
      "1 228\n",
      "1 229\n",
      "1 229\n",
      "1 229\n",
      "1 229\n",
      "1 229\n",
      "1 229\n",
      "1 230\n",
      "1 230\n",
      "1 230\n",
      "1 230\n",
      "1 230\n",
      "1 230\n",
      "1 230\n",
      "1 231\n",
      "1 231\n",
      "1 231\n",
      "1 231\n",
      "1 231\n",
      "1 231\n",
      "1 232\n",
      "1 232\n",
      "1 232\n",
      "1 232\n",
      "1 232\n",
      "1 232\n",
      "1 232\n",
      "1 232\n",
      "1 233\n",
      "1 233\n",
      "1 233\n",
      "1 233\n",
      "1 233\n",
      "1 233\n",
      "1 233\n",
      "1 233\n",
      "1 234\n",
      "1 234\n",
      "1 234\n",
      "1 234\n",
      "1 234\n",
      "1 234\n",
      "1 234\n",
      "1 234\n",
      "1 235\n",
      "1 235\n",
      "1 235\n",
      "1 235\n",
      "1 235\n",
      "1 235\n",
      "1 235\n",
      "1 235\n",
      "1 236\n",
      "1 236\n",
      "1 236\n",
      "1 236\n",
      "1 236\n",
      "1 236\n",
      "1 237\n",
      "1 237\n",
      "1 237\n",
      "1 237\n",
      "1 237\n",
      "1 237\n",
      "1 237\n",
      "1 238\n",
      "1 238\n",
      "1 238\n",
      "1 238\n",
      "1 238\n",
      "1 238\n",
      "1 238\n",
      "1 239\n",
      "1 239\n",
      "1 239\n",
      "1 239\n",
      "1 239\n",
      "1 239\n",
      "1 239\n",
      "1 240\n",
      "1 240\n",
      "1 240\n",
      "1 240\n",
      "1 240\n",
      "1 240\n",
      "1 240\n",
      "1 240\n",
      "1 241\n",
      "1 241\n",
      "1 241\n",
      "1 241\n",
      "1 241\n",
      "1 241\n",
      "1 241\n",
      "1 241\n",
      "1 242\n",
      "1 242\n",
      "1 242\n",
      "1 242\n",
      "1 242\n",
      "1 242\n",
      "1 242\n",
      "1 242\n",
      "1 242\n",
      "1 243\n",
      "1 243\n",
      "1 243\n",
      "1 243\n",
      "1 243\n",
      "1 243\n",
      "1 243\n",
      "1 243\n",
      "1 244\n",
      "1 244\n",
      "1 244\n",
      "1 244\n",
      "1 244\n",
      "1 244\n",
      "1 244\n",
      "1 245\n",
      "1 245\n",
      "1 245\n",
      "1 245\n",
      "1 245\n",
      "1 245\n",
      "1 245\n",
      "1 245\n",
      "1 246\n",
      "1 246\n",
      "1 246\n",
      "1 246\n",
      "1 246\n",
      "1 246\n",
      "1 246\n",
      "1 246\n",
      "1 247\n",
      "1 247\n",
      "1 247\n",
      "1 247\n",
      "1 247\n",
      "1 247\n",
      "1 247\n",
      "1 248\n",
      "1 248\n",
      "1 248\n",
      "1 248\n",
      "1 248\n",
      "1 248\n",
      "1 248\n",
      "1 249\n",
      "1 249\n",
      "1 249\n",
      "1 249\n",
      "1 249\n",
      "1 249\n",
      "1 249\n",
      "1 250\n",
      "1 250\n",
      "1 250\n",
      "1 250\n",
      "1 250\n",
      "1 250\n",
      "1 251\n",
      "1 251\n",
      "1 251\n",
      "1 251\n",
      "1 251\n",
      "1 251\n",
      "1 252\n",
      "1 252\n",
      "1 252\n",
      "1 252\n",
      "1 252\n",
      "1 252\n",
      "1 253\n",
      "1 253\n",
      "1 253\n",
      "1 253\n",
      "1 253\n",
      "1 253\n",
      "1 254\n",
      "1 254\n",
      "1 254\n",
      "1 254\n",
      "1 254\n",
      "1 254\n",
      "1 254\n",
      "1 255\n",
      "1 255\n",
      "1 255\n",
      "1 255\n",
      "1 255\n",
      "1 255\n",
      "1 256\n",
      "1 256\n",
      "1 256\n",
      "1 256\n",
      "1 256\n",
      "1 256\n",
      "1 256\n",
      "1 257\n",
      "1 257\n",
      "1 257\n",
      "1 257\n",
      "1 257\n",
      "1 257\n",
      "1 257\n",
      "1 258\n",
      "1 258\n",
      "1 258\n",
      "1 258\n",
      "1 258\n",
      "1 258\n",
      "1 259\n",
      "1 259\n",
      "1 259\n",
      "1 259\n",
      "1 259\n",
      "1 259\n",
      "1 259\n",
      "1 260\n",
      "1 260\n",
      "1 260\n",
      "1 260\n",
      "1 260\n",
      "1 260\n",
      "1 261\n",
      "1 261\n",
      "1 261\n",
      "1 261\n",
      "1 261\n",
      "1 261\n",
      "1 262\n",
      "1 262\n",
      "1 262\n",
      "1 262\n",
      "1 262\n",
      "1 262\n",
      "1 263\n",
      "1 263\n",
      "1 263\n",
      "1 263\n",
      "1 263\n",
      "1 263\n",
      "1 264\n",
      "1 264\n",
      "1 264\n",
      "1 264\n",
      "1 264\n",
      "1 264\n",
      "1 265\n",
      "1 265\n",
      "1 265\n",
      "1 265\n",
      "1 265\n",
      "1 265\n",
      "1 266\n",
      "1 266\n",
      "1 266\n",
      "1 266\n",
      "1 266\n",
      "1 266\n",
      "1 267\n",
      "1 267\n",
      "1 267\n",
      "1 267\n",
      "1 267\n",
      "1 267\n",
      "1 267\n",
      "1 268\n",
      "1 268\n",
      "1 268\n",
      "1 268\n",
      "1 268\n",
      "1 268\n",
      "1 269\n",
      "1 269\n",
      "1 269\n",
      "1 269\n",
      "1 269\n",
      "1 269\n",
      "1 269\n",
      "1 270\n",
      "1 270\n",
      "1 270\n",
      "1 270\n",
      "1 270\n",
      "1 270\n",
      "1 271\n",
      "1 271\n",
      "1 271\n",
      "1 271\n",
      "1 271\n",
      "1 271\n",
      "1 271\n",
      "1 272\n",
      "1 272\n",
      "1 272\n",
      "1 272\n",
      "1 272\n",
      "1 272\n",
      "1 272\n",
      "1 273\n",
      "1 273\n",
      "1 273\n",
      "1 273\n",
      "1 273\n",
      "1 273\n",
      "1 273\n",
      "1 274\n",
      "1 274\n",
      "1 274\n",
      "1 274\n",
      "1 274\n",
      "1 274\n",
      "1 274\n",
      "1 275\n",
      "1 275\n",
      "1 275\n",
      "1 275\n",
      "1 275\n",
      "1 275\n",
      "1 275\n",
      "1 276\n",
      "1 276\n",
      "1 276\n",
      "1 276\n",
      "1 276\n",
      "1 276\n",
      "1 276\n",
      "1 277\n",
      "1 277\n",
      "1 277\n",
      "1 277\n",
      "1 277\n",
      "1 277\n",
      "1 277\n",
      "1 278\n",
      "1 278\n",
      "1 278\n",
      "1 278\n",
      "1 278\n",
      "1 278\n",
      "1 278\n",
      "1 279\n",
      "1 279\n",
      "1 279\n",
      "1 279\n",
      "1 279\n",
      "1 279\n",
      "1 279\n",
      "1 280\n",
      "1 280\n",
      "1 280\n",
      "1 280\n",
      "1 280\n",
      "1 280\n",
      "1 280\n",
      "1 281\n",
      "1 281\n",
      "1 281\n",
      "1 281\n",
      "1 281\n",
      "1 281\n",
      "1 281\n",
      "1 282\n",
      "1 282\n",
      "1 282\n",
      "1 282\n",
      "1 282\n",
      "1 282\n",
      "1 282\n",
      "1 283\n",
      "1 283\n",
      "1 283\n",
      "1 283\n",
      "1 283\n",
      "1 283\n",
      "1 283\n",
      "1 284\n",
      "1 284\n",
      "1 284\n",
      "1 284\n",
      "1 284\n",
      "1 284\n",
      "1 284\n",
      "1 285\n",
      "1 285\n",
      "1 285\n",
      "1 285\n",
      "1 285\n",
      "1 285\n",
      "1 285\n",
      "1 286\n",
      "1 286\n",
      "1 286\n",
      "1 286\n",
      "1 286\n",
      "1 286\n",
      "1 286\n",
      "1 286\n",
      "1 287\n",
      "1 287\n",
      "1 287\n",
      "1 287\n",
      "1 287\n",
      "1 287\n",
      "1 288\n",
      "1 288\n",
      "1 288\n",
      "1 288\n",
      "1 288\n",
      "1 288\n",
      "1 288\n",
      "1 289\n",
      "1 289\n",
      "1 289\n",
      "1 289\n",
      "1 289\n",
      "1 289\n",
      "1 289\n",
      "1 290\n",
      "1 290\n",
      "1 290\n",
      "1 290\n",
      "1 290\n",
      "1 290\n",
      "1 290\n",
      "1 291\n",
      "1 291\n",
      "1 291\n",
      "1 291\n",
      "1 291\n",
      "1 291\n",
      "1 291\n",
      "1 292\n",
      "1 292\n",
      "1 292\n",
      "1 292\n",
      "1 292\n",
      "1 292\n",
      "1 292\n",
      "1 293\n",
      "1 293\n",
      "1 293\n",
      "1 293\n",
      "1 293\n",
      "1 293\n",
      "1 293\n",
      "1 294\n",
      "1 294\n",
      "1 294\n",
      "1 294\n",
      "1 294\n",
      "1 294\n",
      "1 294\n",
      "1 295\n",
      "1 295\n",
      "1 295\n",
      "1 295\n",
      "1 295\n",
      "1 295\n",
      "1 295\n",
      "1 296\n",
      "1 296\n",
      "1 296\n",
      "1 296\n",
      "1 296\n",
      "1 296\n",
      "1 296\n",
      "1 297\n",
      "1 297\n",
      "1 297\n",
      "1 297\n",
      "1 297\n",
      "1 297\n",
      "1 297\n",
      "1 297\n",
      "1 297\n",
      "1 298\n",
      "1 298\n",
      "1 298\n",
      "1 298\n",
      "1 298\n",
      "1 298\n",
      "1 298\n",
      "1 299\n",
      "1 299\n",
      "1 299\n",
      "1 299\n",
      "1 299\n",
      "1 299\n",
      "1 300\n",
      "1 300\n",
      "1 300\n",
      "1 300\n",
      "1 300\n",
      "1 300\n",
      "1 300\n",
      "1 300\n",
      "1 301\n",
      "1 301\n",
      "1 301\n",
      "1 301\n",
      "1 301\n",
      "1 301\n",
      "1 301\n",
      "1 302\n",
      "1 302\n",
      "1 302\n",
      "1 302\n",
      "1 302\n",
      "1 302\n",
      "1 302\n",
      "1 302\n",
      "1 302\n",
      "1 302\n",
      "1 303\n",
      "1 303\n",
      "1 303\n",
      "1 303\n",
      "1 303\n",
      "1 303\n",
      "1 303\n",
      "1 303\n",
      "1 304\n",
      "1 304\n",
      "1 304\n",
      "1 304\n",
      "1 304\n",
      "1 304\n",
      "1 305\n",
      "1 305\n",
      "1 305\n",
      "1 305\n",
      "1 305\n",
      "1 305\n",
      "1 305\n",
      "1 306\n",
      "1 306\n",
      "1 306\n",
      "1 306\n",
      "1 306\n",
      "1 306\n",
      "1 306\n",
      "1 307\n",
      "1 307\n",
      "1 307\n",
      "1 307\n",
      "1 307\n",
      "1 307\n",
      "1 307\n",
      "1 308\n",
      "1 308\n",
      "1 308\n",
      "1 308\n",
      "1 308\n",
      "1 308\n",
      "1 308\n",
      "1 309\n",
      "1 309\n",
      "1 309\n",
      "1 309\n",
      "1 309\n",
      "1 309\n",
      "1 309\n",
      "1 310\n",
      "1 310\n",
      "1 310\n",
      "1 310\n",
      "1 310\n",
      "1 310\n",
      "1 310\n",
      "1 311\n",
      "1 311\n",
      "1 311\n",
      "1 311\n",
      "1 311\n",
      "1 311\n",
      "1 311\n",
      "1 311\n",
      "1 312\n",
      "1 312\n",
      "1 312\n",
      "1 312\n",
      "1 312\n",
      "1 312\n",
      "1 312\n",
      "1 313\n",
      "1 313\n",
      "1 313\n",
      "1 313\n",
      "1 313\n",
      "1 313\n",
      "1 314\n",
      "1 314\n",
      "1 314\n",
      "1 314\n",
      "1 314\n",
      "1 314\n",
      "1 314\n",
      "1 315\n",
      "1 315\n",
      "1 315\n",
      "1 315\n",
      "1 315\n",
      "1 315\n",
      "1 316\n",
      "1 316\n",
      "1 316\n",
      "1 316\n",
      "1 316\n",
      "1 316\n",
      "1 316\n",
      "1 317\n",
      "1 317\n",
      "1 317\n",
      "1 317\n",
      "1 317\n",
      "1 317\n",
      "1 318\n",
      "1 318\n",
      "1 318\n",
      "1 318\n",
      "1 318\n",
      "1 318\n",
      "1 319\n",
      "1 319\n",
      "1 319\n",
      "1 319\n",
      "1 319\n",
      "1 319\n",
      "1 319\n",
      "1 319\n",
      "1 320\n",
      "1 320\n",
      "1 320\n",
      "1 320\n",
      "1 320\n",
      "1 320\n",
      "1 320\n",
      "1 321\n",
      "1 321\n",
      "1 321\n",
      "1 321\n",
      "1 321\n",
      "1 321\n",
      "1 321\n",
      "1 322\n",
      "1 322\n",
      "1 322\n",
      "1 322\n",
      "1 322\n",
      "1 322\n",
      "1 323\n",
      "1 323\n",
      "1 323\n",
      "1 323\n",
      "1 323\n",
      "1 323\n",
      "1 324\n",
      "1 324\n",
      "1 324\n",
      "1 324\n",
      "1 324\n",
      "1 324\n",
      "1 325\n",
      "1 325\n",
      "1 325\n",
      "1 325\n",
      "1 325\n",
      "1 325\n",
      "1 326\n",
      "1 326\n",
      "1 326\n",
      "1 326\n",
      "1 326\n",
      "1 326\n",
      "1 326\n",
      "1 327\n",
      "1 327\n",
      "1 327\n",
      "1 327\n",
      "1 327\n",
      "1 327\n",
      "1 327\n",
      "1 328\n",
      "1 328\n",
      "1 328\n",
      "1 328\n",
      "1 328\n",
      "1 328\n",
      "1 328\n",
      "1 329\n",
      "1 329\n",
      "1 329\n",
      "1 329\n",
      "1 329\n",
      "1 329\n",
      "1 329\n",
      "1 329\n",
      "1 330\n",
      "1 330\n",
      "1 330\n",
      "1 330\n",
      "1 330\n",
      "1 330\n",
      "1 330\n",
      "1 330\n",
      "1 330\n",
      "1 330\n",
      "1 331\n",
      "1 331\n",
      "1 331\n",
      "1 331\n",
      "1 331\n",
      "1 331\n",
      "1 331\n",
      "1 332\n",
      "1 332\n",
      "1 332\n",
      "1 332\n",
      "1 332\n",
      "1 332\n",
      "1 332\n",
      "1 333\n",
      "1 333\n",
      "1 333\n",
      "1 333\n",
      "1 333\n",
      "1 333\n",
      "1 333\n",
      "1 333\n",
      "1 334\n",
      "1 334\n",
      "1 334\n",
      "1 334\n",
      "1 334\n",
      "1 334\n",
      "1 334\n",
      "1 334\n",
      "1 334\n",
      "1 335\n",
      "1 335\n",
      "1 335\n",
      "1 335\n",
      "1 335\n",
      "1 335\n",
      "1 335\n",
      "1 336\n",
      "1 336\n",
      "1 336\n",
      "1 336\n",
      "1 336\n",
      "1 336\n",
      "1 336\n",
      "1 336\n",
      "1 337\n",
      "1 337\n",
      "1 337\n",
      "1 337\n",
      "1 337\n",
      "1 337\n",
      "1 337\n",
      "1 337\n",
      "1 338\n",
      "1 338\n",
      "1 338\n",
      "1 338\n",
      "1 338\n",
      "1 338\n",
      "1 339\n",
      "1 339\n",
      "1 339\n",
      "1 339\n",
      "1 339\n",
      "1 339\n",
      "1 340\n",
      "1 340\n",
      "1 340\n",
      "1 340\n",
      "1 340\n",
      "1 340\n",
      "1 340\n",
      "1 340\n",
      "1 341\n",
      "1 341\n",
      "1 341\n",
      "1 341\n",
      "1 341\n",
      "1 341\n",
      "1 341\n",
      "1 342\n",
      "1 342\n",
      "1 342\n",
      "1 342\n",
      "1 342\n",
      "1 342\n",
      "1 343\n",
      "1 343\n",
      "1 343\n",
      "1 343\n",
      "1 343\n",
      "1 343\n",
      "1 344\n",
      "1 344\n",
      "1 344\n",
      "1 344\n",
      "1 344\n",
      "1 344\n",
      "1 345\n",
      "1 345\n",
      "1 345\n",
      "1 345\n",
      "1 345\n",
      "1 345\n",
      "1 346\n",
      "1 346\n",
      "1 346\n",
      "1 346\n",
      "1 346\n",
      "1 346\n",
      "1 347\n",
      "1 347\n",
      "1 347\n",
      "1 347\n",
      "1 347\n",
      "1 347\n",
      "1 347\n",
      "1 348\n",
      "1 348\n",
      "1 348\n",
      "1 348\n",
      "1 348\n",
      "1 348\n",
      "1 348\n",
      "1 349\n",
      "1 349\n",
      "1 349\n",
      "1 349\n",
      "1 349\n",
      "1 349\n",
      "1 349\n",
      "1 350\n",
      "1 350\n",
      "1 350\n",
      "1 350\n",
      "1 350\n",
      "1 350\n",
      "1 350\n",
      "1 350\n",
      "1 351\n",
      "1 351\n",
      "1 351\n",
      "1 351\n",
      "1 351\n",
      "1 351\n",
      "1 351\n",
      "1 352\n",
      "1 352\n",
      "1 352\n",
      "1 352\n",
      "1 352\n",
      "1 352\n",
      "1 352\n",
      "1 353\n",
      "1 353\n",
      "1 353\n",
      "1 353\n",
      "1 353\n",
      "1 353\n",
      "1 353\n",
      "1 354\n",
      "1 354\n",
      "1 354\n",
      "1 354\n",
      "1 354\n",
      "1 354\n",
      "1 354\n",
      "1 355\n",
      "1 355\n",
      "1 355\n",
      "1 355\n",
      "1 355\n",
      "1 355\n",
      "1 355\n",
      "1 356\n",
      "1 356\n",
      "1 356\n",
      "1 356\n",
      "1 356\n",
      "1 356\n",
      "1 356\n",
      "1 356\n",
      "1 357\n",
      "1 357\n",
      "1 357\n",
      "1 357\n",
      "1 357\n",
      "1 357\n",
      "1 357\n",
      "1 357\n",
      "1 358\n",
      "1 358\n",
      "1 358\n",
      "1 358\n",
      "1 358\n",
      "1 358\n",
      "1 358\n",
      "1 359\n",
      "1 359\n",
      "1 359\n",
      "1 359\n",
      "1 359\n",
      "1 359\n",
      "1 359\n",
      "1 359\n",
      "1 360\n",
      "1 360\n",
      "1 360\n",
      "1 360\n",
      "1 360\n",
      "1 360\n",
      "1 361\n",
      "1 361\n",
      "1 361\n",
      "1 361\n",
      "1 361\n",
      "1 361\n",
      "1 361\n",
      "1 362\n",
      "1 362\n",
      "1 362\n",
      "1 362\n",
      "1 362\n",
      "1 362\n",
      "1 362\n",
      "1 362\n",
      "1 363\n",
      "1 363\n",
      "1 363\n",
      "1 363\n",
      "1 363\n",
      "1 363\n",
      "1 363\n",
      "1 363\n",
      "1 364\n",
      "1 364\n",
      "1 364\n",
      "1 364\n",
      "1 364\n",
      "1 364\n",
      "1 364\n",
      "1 364\n",
      "1 365\n",
      "1 365\n",
      "1 365\n",
      "1 365\n",
      "1 365\n",
      "1 365\n",
      "1 365\n",
      "1 365\n",
      "1 365\n",
      "1 366\n",
      "1 366\n",
      "1 366\n",
      "1 366\n",
      "1 366\n",
      "1 366\n",
      "1 366\n",
      "1 366\n",
      "1 366\n",
      "1 367\n",
      "1 367\n",
      "1 367\n",
      "1 367\n",
      "1 367\n",
      "1 367\n",
      "1 367\n",
      "1 367\n",
      "1 367\n",
      "1 368\n",
      "1 368\n",
      "1 368\n",
      "1 368\n",
      "1 368\n",
      "1 368\n",
      "1 368\n",
      "1 368\n",
      "1 368\n",
      "1 369\n",
      "1 369\n",
      "1 369\n",
      "1 369\n",
      "1 369\n",
      "1 369\n",
      "1 369\n",
      "1 369\n",
      "1 370\n",
      "1 370\n",
      "1 370\n",
      "1 370\n",
      "1 370\n",
      "1 370\n",
      "1 370\n",
      "1 370\n",
      "1 370\n",
      "1 371\n",
      "1 371\n",
      "1 371\n",
      "1 371\n",
      "1 371\n",
      "1 371\n",
      "1 371\n",
      "1 371\n",
      "1 372\n",
      "1 372\n",
      "1 372\n",
      "1 372\n",
      "1 372\n",
      "1 372\n",
      "1 372\n",
      "1 372\n",
      "1 373\n",
      "1 373\n",
      "1 373\n",
      "1 373\n",
      "1 373\n",
      "1 373\n",
      "1 373\n",
      "1 373\n",
      "1 374\n",
      "1 374\n",
      "1 374\n",
      "1 374\n",
      "1 374\n",
      "1 374\n",
      "1 374\n",
      "1 374\n",
      "1 374\n",
      "1 375\n",
      "1 375\n",
      "1 375\n",
      "1 375\n",
      "1 375\n",
      "1 375\n",
      "1 375\n",
      "1 375\n",
      "1 376\n",
      "1 376\n",
      "1 376\n",
      "1 376\n",
      "1 376\n",
      "1 376\n",
      "1 376\n",
      "1 376\n",
      "1 377\n",
      "1 377\n",
      "1 377\n",
      "1 377\n",
      "1 377\n",
      "1 377\n",
      "1 377\n",
      "1 377\n",
      "1 378\n",
      "1 378\n",
      "1 378\n",
      "1 378\n",
      "1 378\n",
      "1 378\n",
      "1 378\n",
      "1 378\n",
      "1 379\n",
      "1 379\n",
      "1 379\n",
      "1 379\n",
      "1 379\n",
      "1 379\n",
      "1 379\n",
      "1 379\n",
      "1 380\n",
      "1 380\n",
      "1 380\n",
      "1 380\n",
      "1 380\n",
      "1 380\n",
      "1 380\n",
      "1 380\n",
      "1 381\n",
      "1 381\n",
      "1 381\n",
      "1 381\n",
      "1 381\n",
      "1 381\n",
      "1 381\n",
      "1 381\n",
      "1 382\n",
      "1 382\n",
      "1 382\n",
      "1 382\n",
      "1 382\n",
      "1 382\n",
      "1 382\n",
      "1 382\n",
      "1 383\n",
      "1 383\n",
      "1 383\n",
      "1 383\n",
      "1 383\n",
      "1 383\n",
      "1 383\n",
      "1 383\n",
      "1 384\n",
      "1 384\n",
      "1 384\n",
      "1 384\n",
      "1 384\n",
      "1 384\n",
      "1 384\n",
      "1 384\n",
      "1 385\n",
      "1 385\n",
      "1 385\n",
      "1 385\n",
      "1 385\n",
      "1 385\n",
      "1 385\n",
      "1 385\n",
      "1 385\n",
      "1 386\n",
      "1 386\n",
      "1 386\n",
      "1 386\n",
      "1 386\n",
      "1 386\n",
      "1 386\n",
      "1 386\n",
      "1 386\n",
      "1 387\n",
      "1 387\n",
      "1 387\n",
      "1 387\n",
      "1 387\n",
      "1 387\n",
      "1 387\n",
      "1 387\n",
      "1 387\n",
      "1 388\n",
      "1 388\n",
      "1 388\n",
      "1 388\n",
      "1 388\n",
      "1 388\n",
      "1 388\n",
      "1 388\n",
      "1 388\n",
      "1 389\n",
      "1 389\n",
      "1 389\n",
      "1 389\n",
      "1 389\n",
      "1 389\n",
      "1 389\n",
      "1 389\n",
      "1 390\n",
      "1 390\n",
      "1 390\n",
      "1 390\n",
      "1 390\n",
      "1 390\n",
      "1 390\n",
      "1 390\n",
      "1 390\n",
      "1 391\n",
      "1 391\n",
      "1 391\n",
      "1 391\n",
      "1 391\n",
      "1 391\n",
      "1 391\n",
      "1 391\n",
      "1 392\n",
      "1 392\n",
      "1 392\n",
      "1 392\n",
      "1 392\n",
      "1 392\n",
      "1 392\n",
      "1 392\n",
      "1 393\n",
      "1 393\n",
      "1 393\n",
      "1 393\n",
      "1 393\n",
      "1 393\n",
      "1 393\n",
      "1 394\n",
      "1 394\n",
      "1 394\n",
      "1 394\n",
      "1 394\n",
      "1 394\n",
      "1 394\n",
      "1 395\n",
      "1 395\n",
      "1 395\n",
      "1 395\n",
      "1 395\n",
      "1 395\n",
      "1 395\n",
      "1 395\n",
      "1 395\n",
      "1 395\n",
      "1 396\n",
      "1 396\n",
      "1 396\n",
      "1 396\n",
      "1 396\n",
      "1 396\n",
      "1 396\n",
      "1 396\n",
      "1 396\n",
      "1 397\n",
      "1 397\n",
      "1 397\n",
      "1 397\n",
      "1 397\n",
      "1 397\n",
      "1 397\n",
      "1 397\n",
      "1 398\n",
      "1 398\n",
      "1 398\n",
      "1 398\n",
      "1 398\n",
      "1 398\n",
      "1 398\n",
      "1 398\n",
      "1 399\n",
      "1 399\n",
      "1 399\n",
      "1 399\n",
      "1 399\n",
      "1 399\n",
      "1 399\n",
      "1 399\n",
      "1 400\n",
      "1 400\n",
      "1 400\n",
      "1 400\n",
      "1 400\n",
      "1 400\n",
      "1 400\n",
      "1 400\n",
      "1 400\n",
      "1 401\n",
      "1 401\n",
      "1 401\n",
      "1 401\n",
      "1 401\n",
      "1 401\n",
      "1 401\n",
      "1 401\n",
      "1 402\n",
      "1 402\n",
      "1 402\n",
      "1 402\n",
      "1 402\n",
      "1 402\n",
      "1 402\n",
      "1 402\n",
      "1 403\n",
      "1 403\n",
      "1 403\n",
      "1 403\n",
      "1 403\n",
      "1 403\n",
      "1 403\n",
      "1 403\n",
      "1 403\n",
      "1 404\n",
      "1 404\n",
      "1 404\n",
      "1 404\n",
      "1 404\n",
      "1 404\n",
      "1 404\n",
      "1 404\n",
      "1 405\n",
      "1 405\n",
      "1 405\n",
      "1 405\n",
      "1 405\n",
      "1 405\n",
      "1 405\n",
      "1 405\n",
      "1 406\n",
      "1 406\n",
      "1 406\n",
      "1 406\n",
      "1 406\n",
      "1 406\n",
      "1 406\n",
      "1 406\n",
      "1 407\n",
      "1 407\n",
      "1 407\n",
      "1 407\n",
      "1 407\n",
      "1 407\n",
      "1 407\n",
      "1 407\n",
      "1 407\n",
      "1 408\n",
      "1 408\n",
      "1 408\n",
      "1 408\n",
      "1 408\n",
      "1 408\n",
      "1 408\n",
      "1 408\n",
      "1 409\n",
      "1 409\n",
      "1 409\n",
      "1 409\n",
      "1 409\n",
      "1 409\n",
      "1 409\n",
      "1 409\n",
      "1 410\n",
      "1 410\n",
      "1 410\n",
      "1 410\n",
      "1 410\n",
      "1 410\n",
      "1 410\n",
      "1 410\n",
      "1 411\n",
      "1 411\n",
      "1 411\n",
      "1 411\n",
      "1 411\n",
      "1 411\n",
      "1 411\n",
      "1 411\n",
      "1 412\n",
      "1 412\n",
      "1 412\n",
      "1 412\n",
      "1 412\n",
      "1 412\n",
      "1 412\n",
      "1 412\n",
      "1 412\n",
      "1 413\n",
      "1 413\n",
      "1 413\n",
      "1 413\n",
      "1 413\n",
      "1 413\n",
      "1 413\n",
      "1 413\n",
      "1 413\n",
      "1 414\n",
      "1 414\n",
      "1 414\n",
      "1 414\n",
      "1 414\n",
      "1 414\n",
      "1 414\n",
      "1 414\n",
      "1 414\n",
      "1 415\n",
      "1 415\n",
      "1 415\n",
      "1 415\n",
      "1 415\n",
      "1 415\n",
      "1 415\n",
      "1 415\n",
      "1 415\n",
      "1 416\n",
      "1 416\n",
      "1 416\n",
      "1 416\n",
      "1 416\n",
      "1 416\n",
      "1 416\n",
      "1 416\n",
      "1 416\n",
      "1 417\n",
      "1 417\n",
      "1 417\n",
      "1 417\n",
      "1 417\n",
      "1 417\n",
      "1 417\n",
      "1 417\n",
      "1 417\n",
      "1 418\n",
      "1 418\n",
      "1 418\n",
      "1 418\n",
      "1 418\n",
      "1 418\n",
      "1 418\n",
      "1 418\n",
      "1 418\n",
      "1 419\n",
      "1 419\n",
      "1 419\n",
      "1 419\n",
      "1 419\n",
      "1 419\n",
      "1 419\n",
      "1 419\n",
      "1 419\n",
      "1 420\n",
      "1 420\n",
      "1 420\n",
      "1 420\n",
      "1 420\n",
      "1 420\n",
      "1 420\n",
      "1 420\n",
      "1 420\n",
      "1 421\n",
      "1 421\n",
      "1 421\n",
      "1 421\n",
      "1 421\n",
      "1 421\n",
      "1 421\n",
      "1 421\n",
      "1 422\n",
      "1 422\n",
      "1 422\n",
      "1 422\n",
      "1 422\n",
      "1 422\n",
      "1 422\n",
      "1 422\n",
      "1 423\n",
      "1 423\n",
      "1 423\n",
      "1 423\n",
      "1 423\n",
      "1 423\n",
      "1 423\n",
      "1 423\n",
      "1 424\n",
      "1 424\n",
      "1 424\n",
      "1 424\n",
      "1 424\n",
      "1 424\n",
      "1 424\n",
      "1 424\n",
      "1 425\n",
      "1 425\n",
      "1 425\n",
      "1 425\n",
      "1 425\n",
      "1 425\n",
      "1 425\n",
      "1 425\n",
      "1 425\n",
      "1 426\n",
      "1 426\n",
      "1 426\n",
      "1 426\n",
      "1 426\n",
      "1 426\n",
      "1 426\n",
      "1 426\n",
      "1 426\n",
      "1 427\n",
      "1 427\n",
      "1 427\n",
      "1 427\n",
      "1 427\n",
      "1 427\n",
      "1 427\n",
      "1 427\n",
      "1 428\n",
      "1 428\n",
      "1 428\n",
      "1 428\n",
      "1 428\n",
      "1 428\n",
      "1 428\n",
      "1 428\n",
      "1 428\n",
      "1 429\n",
      "1 429\n",
      "1 429\n",
      "1 429\n",
      "1 429\n",
      "1 429\n",
      "1 429\n",
      "1 429\n",
      "1 429\n",
      "1 430\n",
      "1 430\n",
      "1 430\n",
      "1 430\n",
      "1 430\n",
      "1 430\n",
      "1 430\n",
      "1 430\n",
      "1 430\n",
      "1 431\n",
      "1 431\n",
      "1 431\n",
      "1 431\n",
      "1 431\n",
      "1 431\n",
      "1 431\n",
      "1 431\n",
      "1 431\n",
      "1 432\n",
      "1 432\n",
      "1 432\n",
      "1 432\n",
      "1 432\n",
      "1 432\n",
      "1 432\n",
      "1 432\n",
      "1 433\n",
      "1 433\n",
      "1 433\n",
      "1 433\n",
      "1 433\n",
      "1 433\n",
      "1 433\n",
      "1 433\n",
      "1 434\n",
      "1 434\n",
      "1 434\n",
      "1 434\n",
      "1 434\n",
      "1 434\n",
      "1 434\n",
      "1 435\n",
      "1 435\n",
      "1 435\n",
      "1 435\n",
      "1 435\n",
      "1 435\n",
      "1 435\n",
      "1 435\n",
      "1 435\n",
      "1 436\n",
      "1 436\n",
      "1 436\n",
      "1 436\n",
      "1 436\n",
      "1 436\n",
      "1 436\n",
      "1 436\n",
      "1 437\n",
      "1 437\n",
      "1 437\n",
      "1 437\n",
      "1 437\n",
      "1 437\n",
      "1 437\n",
      "1 437\n",
      "1 438\n",
      "1 438\n",
      "1 438\n",
      "1 438\n",
      "1 438\n",
      "1 438\n",
      "1 438\n",
      "1 438\n",
      "1 439\n",
      "1 439\n",
      "1 439\n",
      "1 439\n",
      "1 439\n",
      "1 439\n",
      "1 439\n",
      "1 440\n",
      "1 440\n",
      "1 440\n",
      "1 440\n",
      "1 440\n",
      "1 440\n",
      "1 441\n",
      "1 441\n",
      "1 441\n",
      "1 441\n",
      "1 441\n",
      "1 441\n",
      "1 441\n",
      "1 442\n",
      "1 442\n",
      "1 442\n",
      "1 442\n",
      "1 442\n",
      "1 442\n",
      "1 443\n",
      "1 443\n",
      "1 443\n",
      "1 443\n",
      "1 443\n",
      "1 443\n",
      "1 444\n",
      "1 444\n",
      "1 444\n",
      "1 444\n",
      "1 444\n",
      "1 444\n",
      "1 445\n",
      "1 445\n",
      "1 445\n",
      "1 445\n",
      "1 445\n",
      "1 445\n",
      "1 446\n",
      "1 446\n",
      "1 446\n",
      "1 446\n",
      "1 446\n",
      "1 446\n",
      "1 447\n",
      "1 447\n",
      "1 447\n",
      "1 447\n",
      "1 447\n",
      "1 447\n",
      "1 448\n",
      "1 448\n",
      "1 448\n",
      "1 448\n",
      "1 448\n",
      "1 448\n",
      "1 449\n",
      "1 449\n",
      "1 449\n",
      "1 449\n",
      "1 449\n",
      "1 450\n",
      "1 450\n",
      "1 450\n",
      "1 450\n",
      "1 450\n",
      "1 451\n",
      "1 451\n",
      "1 451\n",
      "1 451\n",
      "1 451\n",
      "1 452\n",
      "1 452\n",
      "1 452\n",
      "1 452\n",
      "1 452\n",
      "1 453\n",
      "1 453\n",
      "1 453\n",
      "1 453\n",
      "1 453\n",
      "1 454\n",
      "1 454\n",
      "1 454\n",
      "1 454\n",
      "1 454\n",
      "1 455\n",
      "1 455\n",
      "1 455\n",
      "1 455\n",
      "1 455\n",
      "1 456\n",
      "1 456\n",
      "1 456\n",
      "1 456\n",
      "1 456\n",
      "1 456\n",
      "1 457\n",
      "1 457\n",
      "1 457\n",
      "1 457\n",
      "1 457\n"
     ]
    }
   ],
   "source": [
    "import cv2\n",
    "\n",
    "\n",
    "def recognize(campath):\n",
    "    \n",
    "    recognizer = cv2.face.LBPHFaceRecognizer_create()\n",
    "\n",
    "    recognizer.read('cascades/trainer.yml')\n",
    "\n",
    "    cascadePath = \"haarcascade_frontalface_default.xml\"\n",
    "\n",
    "    faceCascade = cv2.CascadeClassifier(cascadePath)\n",
    "    # 字体\n",
    "    font = cv2.FONT_HERSHEY_DUPLEX\n",
    "    names = ['王二麻子','张三','李四']\n",
    "    video= cv2.VideoCapture(campath)\n",
    "    \n",
    "\t# 加载人脸识别数据库和眼睛识别数据库\n",
    "    faceCascadePath = \"cascades/haarcascade_frontalface_default.xml\"\n",
    "    profiefaceCascadePath = \"cascades/haarcascade_profileface.xml\"\n",
    "    eyeCascadePath  = \"cascades/haarcascade_eye.xml\"\n",
    "    #\n",
    "    faceCascade = cv2.CascadeClassifier(faceCascadePath)\n",
    "    eyeCascade  = cv2.CascadeClassifier(eyeCascadePath)\n",
    "    ProfilefaceCascade = cv2.CascadeClassifier(profiefaceCascadePath)\n",
    "    ii=1 \n",
    "    while True:\n",
    "\n",
    "        #读取视频\n",
    "        (grabbed,raw_frame) = video.read()\n",
    "    \t# 进行图像缩放\n",
    "        (height,width) = raw_frame.shape[:2]\n",
    "        ratio = 900/width\n",
    "        dim = (900,int(height*ratio))\n",
    "        frame = cv2.resize(raw_frame,dim,interpolation=cv2.INTER_AREA)\n",
    "        \n",
    "        grayframe = cv2.cvtColor(frame,cv2.COLOR_BGR2GRAY)\n",
    "        # 进行灰度处理\n",
    "        # 进行人脸识别，返回人脸所在的矩形\n",
    "        faceRects = faceCascade.detectMultiScale(grayframe,\\\n",
    "                                                 scaleFactor = 1.1, \\\n",
    "                                                 minNeighbors = 5, \\\n",
    "                                                 minSize = (30, 30),\\\n",
    "                                                 flags = cv2.CASCADE_SCALE_IMAGE)\n",
    "        faceRects_list=[]\n",
    "        eyesRects_list=[]                                       \n",
    "        \n",
    "        for (fx,fy,fw,fh) in faceRects: \n",
    "            \n",
    "            # region of interest:faceROI\n",
    "            faceROI = grayframe[fy:fy+fh,fx:fx+fw]\n",
    "            # 以两个对角线坐标的形式保存\n",
    "            faceRects_list.append((fx,fy,fx+fw,fy+fh))\n",
    "            # 进行眼睛识别，返回眼睛所在的矩形\n",
    "            eyeRects = eyeCascade.detectMultiScale(faceROI,\\\n",
    "                                                   scaleFactor = 1.01, \\\n",
    "                                                   minNeighbors = 3, \\\n",
    "                                                   minSize = (30, 30),\\\n",
    "                                                   flags = cv2.CASCADE_SCALE_IMAGE)\n",
    "            for (ex,ey,ew,eh) in eyeRects:\n",
    "                # 同样也以两个对角线坐标的形式保存，注意眼睛的参考坐标系是faceROI\n",
    "                eyesRects_list.append((fx+ex,fy+ey,fx+ex+ew,fy+ey+eh))\n",
    "        \n",
    "        # 在视频帧上绘制出识别出来的矩形框框\n",
    "        for rect in faceRects:\n",
    "            (x,y,w,h) = rect\n",
    "            cv2.rectangle(frame,(x,y),(x+w,y+h),(0,255,0),2)\n",
    "            faceROI = grayframe[fy:fy+fh,fx:fx+fw]\n",
    "            idnum, confidence = recognizer.predict(faceROI)\n",
    "            print(idnum,ii)\n",
    "            if confidence < 100:\n",
    "                    idnum = names[idnum]\n",
    "                    confidence = \"{0}%\".format(round(100 - confidence))\n",
    "            else:\n",
    "                    idnum = \"unknown\"\n",
    "                    confidence = \"{0}%\".format(round(100 - confidence))\n",
    "            cv2.putText(frame, str(idnum), (x+5, y-5), font, 1, (0, 0, 255), 1)\n",
    "            cv2.putText(frame, str(confidence), (x+5, y+h-5), font, 1, (0, 0, 0), 1)\n",
    "        cv2.imshow(\"tracking\",frame)\n",
    "        ii=ii+1\n",
    "        # 等待1ms\n",
    "        \n",
    "        if cv2.waitKey(1)&0xFF == ord('q'):\n",
    "            break\n",
    "\n",
    "    video.release()\n",
    "    cv2.destroyAllWindows()\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "\n",
    "    videoPath = \"./video/img_4524.mp4\"\n",
    "    recognize(videoPath)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "python310",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.15"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "a888cd810c90be07c3c921372a6d7ff433f5a38d5779dfb2a871d99db75673fb"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
